
import java.util.*;


class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


/*
    @author TTDB
    @create 2025/9/4
    @description: 之字型遍历
*/
public class zigzagLevelOrder {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null){
            return List.of();
        }
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while(!q.isEmpty()){
            int n = q.size();
            List<Integer> vals = new ArrayList<>(n);
            while(n-- > 0){
                TreeNode node = q.poll();
                vals.add(node.val);
                if(node.left != null) q.add(node.left);
                if(node.right != null) q.add(node.right);
            }
            //翻转api
            if (ans.size() % 2 > 0) Collections.reverse(vals);
            ans.add(vals);
        }
        return ans;
    }

    //LinkedList双端队列
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            //锯齿性的层序遍历
            //使用双端的队列，规定奇数层添加到tmp的尾部，偶数层添加到tmp的头部
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> res = new ArrayList<>();
            if(root != null){
                queue.add(root);
            }
            while(!queue.isEmpty()){
                LinkedList<Integer> tmp = new LinkedList<>();
                int size = queue.size();
                for(int i = 0 ;i < size ;i ++){
                    TreeNode node =queue.poll();
                    if(res.size() %2 == 0){
                        tmp.addLast(node.val);
                    }else{
                        tmp.addFirst(node.val);
                    }
                    if(node.left != null){
                        queue.add(node.left);
                    }
                    if(node.right != null){
                        queue.add(node.right);
                    }

                }
                res.add(tmp);
            }
            return res;
        }
    }
}
